"""
顺序表和链表的区标：
顺序表：地址空间连续
    优点：遍历、查找很方便
    缺点：添加、删除元素很麻烦
链表：地址空间不一定连续
    优点：添加、删除元素很方便（只需要知道节点的地址即可）
    缺点：遍历、查找很麻烦（必须知道下一个节点的地址）
这节课学习单向链表
每次定义head头指针指向头节点
两部分：1：数据域（存储节点自身的地址）  2：指针域（存储下一个节点的地址）
"""


# 使用面向对象思想去完成
# 定义一个节点类
class Node:
    # 定义节点类的初始化方法
    def __init__(self, data):  # init系统自带的，构造方法：创建对象，init自己执行
        # 数据域（存储节点自身的数据）
        self.data = data
        # 指针域（存储下一个节点的地址）初始化指向空
        self.next = None


# 定义单向链表类
class SinglyLink:
    # 定义单向链表类的初始化方法
    def __init__(self):
        # 定义头指针，永远指向头节点
        self.head = None

    # 定义实现单向链表类的各种操作
    # 定义判断单向链表是否为空的方法
    def isEmpty(self):
        # 如果头指针head指向为空
        if self.head == None:
            return True
        else:
            return False

    # 插入节点：头插法，尾插法，向指定位置插入方法
    # 定义头插法（向链表的头部插入新节点）
    def insertToHead(self, value):  # value表示新插入节点的数据域
        # 插入节点之前，必须创建一个节点对象
        node = Node(value)  # 1
        # 分情况
        # 1：当链表为空时
        if self.isEmpty() == True:
            # 直接让头指针指向新插入的节点即可
            self.head = node
            return
        else:
            # 2：当链表不为空时
            # 先让新插入的节点的指针域指向原来的头节点
            node.next = self.head
            # 再让头指针指向新插入的节点
            self.head = node

    # 定义一个实现尾插节点的方法（插入到末端）   5 4 3 2 1 6 7 8 9 10
    def insertToTail(self, value):
        node = Node(value)
        if self.isEmpty() == True:
            # 直接让头指针指向新插入的节点即可
            self.head = node
            return
        else:
            # 定义临时指针节点，从头节点开始
            temp = self.head
            while (
                temp.next != None
            ):  # 循环结束后，temp的指针域正好为空，所以要在temp的指针域不为空里面循环
                # temp后移
                temp = temp.next
            # 再让temp的指针域指向新插入的节点
            temp.next = node

    # 定义向指定位置插入节点的方法: 设向下标位置为5的地方插入新节点520   新链表：5 4 3 2 1 520 6 7 8 9 10
    def insertToPos(self, pos, value):  # pos位置 value节点的数据域
        node = Node(value)
        if self.isEmpty() == True:
            # 直接让头指针指向新插入的节点即可
            self.head = node
            return
        else:
            i = 0  # 信号量，方便控制循环
            temp = self.head
            while (
                i != pos - 1
            ):  # 当循环结束：i的值正好等于位置-1，所以在i的值不等于位置-1里面循环
                # temp后移
                temp = temp.next
                i += 1
            # 如果循环结束了，说明temp肯定停在1号
            # 1：先让新插入的节点的指针域指向6号（temp的下一个）
            node.next = temp.next
            # 2:再让temp的指针域指向新插入的节点
            temp.next = node

    # 定义删除头节点的方法     4 3 2 1 520 6 7 8 9 10
    def deleteHead(self):
        # 如果链表为空，则退出
        if self.isEmpty() == True:
            print("此链表为空，禁止删除！")
            return
        else:
            # 直接让头指针指向原来的头节点的指针域
            self.head = self.head.next

    # 定义一个遍历单向链表的方法（从head开始去遍历）
    def travel(self):
        # 假设这个链表空
        if self.isEmpty() == True:
            print("链表为空，无法遍历！")
            return
        else:
            # 定义临时节点，指向头节点
            temp = self.head
            # 当循环结束之后，temp指向为空。所以在temp不为空里面去循环。
            while temp != None:
                # 先打印出当前节点的数据域
                print(temp.data, end=" ")
                # 再让临时节点后移
                temp = temp.next
            print()

    # 定义删除尾节点的方法
    def deleteTail(self):
        # 如果链表为空，则无需删除
        if self.isEmpty():
            print("链表为空，无法删除尾节点！")
            return
        # 如果链表只有一个节点，则直接将头节点置空即可
        if self.head.next is None:
            self.head = None
            return
        # 否则，需要找到尾节点的前一个节点
        temp = self.head
        while temp.next.next is not None:  # 循环找到尾节点的前一个节点
            temp = temp.next
        # 将尾节点的前一个节点的指针域置空，即删除尾节点
        temp.next = None

    # 定义查找方法
    def search(self, value):
        current = self.head  # 从头节点开始遍历
        while current is not None:  # 遍历链表直到current为None
            if current.data == value:  # 如果找到匹配的节点
                print("存在{}号，查找成功".format(value))
                return True  # 返回True表示查找成功
            current = current.next  # 移动到下一个节点
        print("不存在，查找失败")
        return False  # 返回False表示查找失败


if __name__ == "__main__":
    # 创建一个单向链表类型的对象
    singlylink = SinglyLink()
    if singlylink.isEmpty() == True:
        print("单向链表为空！")
    else:
        print("单向链表不为空！")
    print("使用头插法的结果：")
    # 自己使用循环，将76-80，插入1 2 3 4 5
    for i in range(1, 6):
        singlylink.insertToHead(i)
    singlylink.travel()
    # 尾插法：新插入的节点立刻成为尾节点  6 7 8 9 10     =》  5 4 3 2 1 6 7 8 9 10
    i = 6
    while i <= 10:
        singlylink.insertToTail(i)
        i += 1
    print("尾插法的结果：")
    singlylink.travel()
    print("向第五个位置插入节点520号：")
    singlylink.insertToPos(5, 520)
    singlylink.travel()
    print("删除头节点的结果：")
    singlylink.deleteHead()
    singlylink.travel()
    print("删除尾节点")
    singlylink.deleteTail()
    singlylink.travel()
    print("查找520号")
    singlylink.search(520)
    # 课后作业：
    # 1：定义删除尾节点的方法（打印结果：4 3 2 1 520 6 7 8 9）
    # 2：定义查找某个数据域是否存在于链表中，设传入520，则打印出：存在520号，查找成功，否则:不存在，查找失败
    # 周日交周文乐    1：代码、运行结果截图、作业评分表（作业2：单向链表的操作）
    # 周日，飞哥有事，数据结构停课！
